package geekstudy.week3;

import java.util.*;

/**
 *
 * https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/comments/
 * 429. N 叉树的层序遍历
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：2 ms, 在所有 Java 提交中击败了88.54% 的用户
 * 内存消耗：39.5 MB, 在所有 Java 提交中击败了14.47% 的用户
 *
 *
 */
public class Week3NAryTreeLevelOrderTraversal {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levelList = new ArrayList<List<Integer>>();
        if(root != null) {
            List<Integer> rootLevelList = new ArrayList<Integer>();
            rootLevelList.add(root.val);
            levelList.add(rootLevelList);

            Map<Integer, List<Integer>> levelListMap = new LinkedHashMap<Integer, List<Integer>>();
            if(root.children != null && root.children.size() > 0) {
                levelListMap(root.children, levelListMap, 1);
            }
            levelList.addAll(levelListMap.values());

        }
        return levelList;
    }

    private void levelListMap(List<Node> childrenList, Map<Integer, List<Integer>> levelListMap, int level) {

        for(Node node : childrenList) {
            mapPutVal(levelListMap, level, node.val);
            if(node.children != null && node.children.size() > 0) {
                levelListMap(node.children, levelListMap, level + 1);
            }
        }
        //return levelMap;
    }

    private void mapPutVal(Map<Integer, List<Integer>> levelListMap, int level, int value) {
        if(!levelListMap.containsKey(level)) {
            List<Integer> list = new ArrayList<Integer>();
            levelListMap.put(level, list);
        }
        levelListMap.get(level).add(value);
    }
}
